package jjn.carl.greedy;

import java.util.Scanner;

/**
 * @author Jjn
 * @since 2023/7/29 20:20
 */
public class LeetCode45 {
    public int jump(int[] nums) {
        int k = 0;
        //记录跳跃的次数
        int step = 0;
        int end = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //一定跳得到，因此不存在 k < i
            k = Math.max(k, i + nums[i]);
            //第一次起跳 或 到达跳跃的边界
            if (i == end) {
                //再次起跳
                step++;
                //更新边界
                end = k;
            }
        }
        return step;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] nums = new int[total];
        for (int i = 0; i < total; i++) {
            nums[i] = scanner.nextInt();
        }
        int jump = new LeetCode45().jump(nums);
        System.out.println(jump);
    }
}
